#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    map<int,int> mp, cnt;
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    if(k == 2) {
        for(auto x : a) {
            if(x % 2 == 0) {
                cout << 0 << endl;
                return;
            }
        }
        cout << 1 << endl;
    } else if(k == 3) {
        int mx = 2;
        for(auto x : a) {
            mx = min(mx, 3 - x % 3);
            if(x % 3 == 0) {
                cout << 0 << endl;
                return;
            }
        }
        cout << mx << endl;
    }else if(k == 5) {
        int mx = 4;
        for(auto x : a) {
            mx = min(mx, 5 - x % 5);
            if(x % 5 == 0) {
                cout << 0 << endl;
                return;
            }
        }
        cout << mx << endl;
    } else{
        int mx = 4, cnt = 0;
        for(auto x : a) {
            mx = min(mx, 4 - x % 4);
            if(x % 2 == 0) cnt++;
            if(x % 4 == 0) {
                cout << 0 << endl;
                return;
            }
        }
        if(cnt >= 2) {
            cout << 0 << endl;
            return;
        }
        if(cnt == 1) {
            cout << 1 << endl;
            return;
        }
        cout << min(2, mx) << endl;
    }
}

int main() {
    int t;
    cin >> t;
    while(t--) solve();
    return 0;
}